package practice;

/**
 * 扁平化嵌套列表迭代器
 * 给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
 * <p>
 * 列表中的项或者为一个整数，或者是另一个列表。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [[1,1],2,[1,1]]
 * 输出: [1,1,2,1,1]
 * 解释: 通过重复调用 next 直到 hasNext 返回false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
 * 示例 2:
 * <p>
 * 输入: [1,[4,[6]]]
 * 输出: [1,4,6]
 * 解释: 通过重复调用 next 直到 hasNext 返回false，next 返回的元素的顺序应该是: [1,4,6]。
 */

import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 */
interface NestedInteger {
    // @return true if this NestedInteger holds a single integer, rather than a nested list.
    public boolean isInteger();

    // @return the single integer that this NestedInteger holds, if it holds a single integer
    // Return null if this NestedInteger holds a nested list
    public Integer getInteger();

    // @return the nested list that this NestedInteger holds, if it holds a nested list
    // Return null if this NestedInteger holds a single integer
    public List<NestedInteger> getList();
}

/**
 * 思路：使用栈保存状态，当访问主list的元素为integer，返回，否则遍历子list元素并存入stack中
 * 下一次调用hasNext()时，先判断栈是否为空，不为空则继续遍历之前的子list，否则遍历主list下一个元素
 */
public class _341_FlattenNestedListIterator implements Iterator<Integer> {


    Iterator<NestedInteger> iterator;
    NestedInteger holder;
    Stack<_341_FlattenNestedListIterator> stack;

    public _341_FlattenNestedListIterator(List<NestedInteger> nestedList) {
        iterator = nestedList.iterator();
        stack = new Stack<>();
    }

    @Override
    public Integer next() {
        return holder.getInteger();
    }

    @Override
    public boolean hasNext() {
        if (stack.isEmpty() && !iterator.hasNext()) {
            return false;
        }
        NestedInteger nestedInteger;
        if(stack.isEmpty()) {
            nestedInteger = iterator.next();
        } else {
            _341_FlattenNestedListIterator tmpIterator = stack.peek();
            if(tmpIterator.hasNext()) {
                holder = tmpIterator.holder;
                return true;
            } else {
                stack.pop();
                if(iterator.hasNext()){
                    nestedInteger = iterator.next();
                } else {
                    return false;
                }
            }
        }
        if (nestedInteger.isInteger()) {
            holder = nestedInteger;
            return true;
        } else {
            _341_FlattenNestedListIterator tmpIterator = new _341_FlattenNestedListIterator(nestedInteger.getList());
            stack.push(tmpIterator);
            boolean tmpHasNext = tmpIterator.hasNext();
            if (tmpHasNext) {
                holder = tmpIterator.holder;
            }
            return tmpHasNext || hasNext();
        }
    }
}
